{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 010. Regular Expression Matching 正则表达式匹配\n",
    "\n",
    "### 难度：Hard\n",
    "\n",
    "## 刷题内容\n",
    "\n",
    "> 原题链接\n",
    "\n",
    " - 中文：https://leetcode-cn.com/problems/two-sum/description\n",
    " - 英文：https://leetcode.com/problems/two-sum\n",
    "\n",
    "> 内容描述\n",
    "\n",
    "```\n",
    "给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。\n",
    "\n",
    "'.' 匹配任意单个字符。\n",
    "'*' 匹配零个或多个前面的元素。\n",
    "匹配应该覆盖整个字符串 (s) ，而不是部分字符串。\n",
    "\n",
    "说明:\n",
    " - s 可能为空，且只包含从 a-z 的小写字母。\n",
    " - p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。\n",
    "\n",
    "示例 1:\n",
    "输入:\n",
    "s = \"aa\"\n",
    "p = \"a\"\n",
    "输出: false\n",
    "解释: \"a\" 无法匹配 \"aa\" 整个字符串。\n",
    "\n",
    "示例 2:\n",
    "输入:\n",
    "s = \"aa\"\n",
    "p = \"a*\"\n",
    "输出: true\n",
    "解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 \"aa\"。\n",
    "\n",
    "示例 3:\n",
    "输入:\n",
    "s = \"ab\"\n",
    "p = \".*\"\n",
    "输出: true\n",
    "解释: \".*\" 表示可匹配零个或多个('*')任意字符('.')。\n",
    "\n",
    "示例 4:\n",
    "输入:\n",
    "s = \"aab\"\n",
    "p = \"c*a*b\"\n",
    "输出: true\n",
    "解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 \"aab\"。\n",
    "\n",
    "示例 5:\n",
    "输入:\n",
    "s = \"mississippi\"\n",
    "p = \"mis*is*p*.\"\n",
    "输出: false\n",
    "```\n",
    "\n",
    "## 解题方案\n",
    "\n",
    "> 思路 1\n",
    "\n",
    "暴力法。Lisanaaa 大佬想出来的，不得不赞一个，哈哈哈。之前想暴力法，把脑袋想爆掉了都没想全各种情况。那么，看看他是怎么解的吧。\n",
    "\n",
    "\".\" 很容易处理。难点就在 \"*\" 身上， \"*\" 是不会单独的，它一定是和前面的 一个字母或者 \".\" 配成一对 出现的。看成一对后是这样子的 \"X*\" ，它的性质是：要么匹配 0 个，要么匹配连续的 \"X\" 。所以尝试暴力法的时候一个 trick 是从后往前匹配。\n",
    "\n",
    "暴力解法也是可以 AC 的。\n",
    "\n",
    "下面这样来分情况：\n",
    "\n",
    " - 如果 s[i] = p[j] 或者 p[j]= . ： 往前匹配一位\n",
    " - 如果 p[j] = ' * ' , 检查一下，如果这个时候 p[j-1] = . 或者 p[j-1] = s[i] ，那么就往前匹配，如果这样能匹配过，就 return True ， 否者我们忽略 'X* ' ,这里注意里面的递推关系。\n",
    " - 再处理一下边界情况：\n",
    "  - s 已经匹配完了， 如果此时 p 还有，那么如果剩下的是 X* 这种可以过，所以需要检查一下\n",
    "  - p 匹配完毕，如果 s 还有没有匹配的话，那么就 return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def isMatch(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def helper(s, i, p, j):\n",
    "            if j == -1:\n",
    "                return i == -1\n",
    "            if i == -1:\n",
    "                if p[j] != '*':\n",
    "                    return False\n",
    "                return helper(s, i, p, j-2)\n",
    "            if p[j] == '*':\n",
    "                if p[j-1] == '.' or p[j-1] == s[i]:\n",
    "                    if helper(s, i-1, p, j):\n",
    "                        return True\n",
    "                return helper(s, i, p, j-2)\n",
    "            if p[j] == '.' or p[j] == s[i]:\n",
    "                return helper(s, i-1, p, j-1)\n",
    "            return False\n",
    "\n",
    "        return helper(s, len(s)-1, p, len(p)-1)\n",
    "    \n",
    "s = 'abc'\n",
    "p = 'a*abc'\n",
    "ss = Solution()\n",
    "print(ss.isMatch(s, p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 思路 2\n",
    "\n",
    "动态规划 解法。\n",
    "\n",
    "dp 优化，感觉和 edit distance 很像。DP优化待代码化，感觉学DP的一个重点除了递归学好以外，另一点是一定要会画表格。\n",
    "\n",
    "画一个表格来看一下状况\n",
    "\n",
    "```\n",
    "\t\t\tc\t*\ta\t*\tb\n",
    "\t\t0\t1\t2\t3\t4\t5\n",
    "\t0\t1\t0\t1\t0\t1\t0\t\t\n",
    "a\t1\t0\t0\t0\t1\t1\t0\t\t\t\t\t\n",
    "a\t2\t0\t0\t0\t0\t1\t0\t\t\t\t\t\n",
    "b\t3\t0\t0\t0\t0\t0\t1\t\t\t\n",
    "```\n",
    "\n",
    "这里有几个取巧/容易出问题的敌方，这里画的表用的是1-based string。一上来，做的事包括：\n",
    "\n",
    " - 初始化，空字符匹配：dp[0][0] =1\n",
    " - 第一行， c * 可以匹配空字符， c * a * 可以匹配空字符， p[j-1] != s[i] ，匹配空字符\n",
    " - 然后进入第二行再来看，实际上我们可以看到，如果没有碰到 * 匹配还是很朴素的，但是碰到 * ：\n",
    "  - 1 这个匹配可以从左侧传来，dp[i][j] = dp[i][j-1] ，that is 匹配 1 个\n",
    "  - 1 也可以有上方传来，这种情况是 p[j-1] = s[i] ，匹配多个 dp[i][j] = dp[i-1][j]\n",
    "  - 1 这个匹配也可以从间隔一个的左侧传来，that is 也可以有个性的匹配 0 个,如同匹配空字符一样 dp[i][j] = dp[i][j-2] ，但是注意匹配 0 个实际上有两种状况，如果 p[j-1]!=s[i] ,强制匹配 0 个，即使 p[j-1] == s[i] ,我们也可以傲娇的用它来匹配 0 个。\n",
    "  \n",
    "再代码化一点：\n",
    "\n",
    " - s[i] == p[j] 或者 p[j] == '.' : dp[i][j] = dp[i-1][j-1]\n",
    " - p[j] == '*' : 然后分几种情况\n",
    "  - p[j-1] != s[i] : dp[i][j] = dp[i][j-2] 匹配 0 个的状况\n",
    "  - p[j-1] == s[i] or p[i-1] == '.':\n",
    "    - dp[i][j] = dp[i-1][j] 匹配多个 s[i]\n",
    "    - dp[i][j] = dp[i][j-2] 匹配 0 个\n",
    "\n",
    "AC 代码，注意一下，因为上表为了表达方便，用的是 1-based string 系统，实际写代码的时候我们心里还是清楚这个 string 还是从 0 开始的，不过也可以尝试往前面添东西来方便。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def isMatch(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        m, n = len(s), len(p)\n",
    "        dp = [ [0 for i in range(n+1)] for j in range(m+1)]\n",
    "\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        # init the first line\n",
    "        for i in range(2,n+1):\n",
    "            if p[i-1] == '*':\n",
    "                dp[0][i] = dp[0][i-2]\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if p[j-1] == '*':\n",
    "                    if p[j-2] != s[i-1] and p[j-2] != '.':\n",
    "                        dp[i][j] = dp[i][j-2]\n",
    "                    elif p[j-2] == s[i-1] or p[j-2] == '.':\n",
    "                        dp[i][j] = dp[i-1][j] or dp[i][j-2]\n",
    "\n",
    "                elif s[i-1] == p[j-1] or p[j-1] == '.':\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "\n",
    "        return dp[m][n] == 1 \n",
    "    \n",
    "s = 'abc'\n",
    "p = 'a*abc'\n",
    "ss = Solution()\n",
    "print(ss.isMatch(s, p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我做的动态规划和上面大体思路是类似的。\n",
    "\n",
    "直接说动态转移方程组了，我们首先定义一些变量方便解释，被匹配串为s，模式串为p。状态转移数组 dp[i][j]表示利用 p 的前 j 个字符匹配 s 的前 i 个字符的匹配结果（成功为 true，失败为 false）。\n",
    "\n",
    " - **s[i] == p[j] || p[j] == '.'** ，那么 dp[i][j] = dp[i-1][j-1] ，也就是既然 s 串的第 i 个字符能和 p 串的第 j 个字符匹配，那么如果 s 串的前 i-1 个字符和 p 串的前 j-1 个字符能匹配则 s 串的前 i 个和 p 串的前 j 个则能匹配，反之不能。\n",
    " - **p[j] == '*'** ：分情况讨论。\n",
    "   - **s[i] != p[j-1] && p[j-1] != '.'** ，那么 dp[i][j] = dp[i][j-2] ，也就是 * 号前面的那个字符在匹配的过程当中一个都不使用。\n",
    "   - **else，那么dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2]**，也就是说要么使用 '*' 号进行匹配( dp[i-1][j] )，要么只使用 '*' 号前面的那个字符匹配，不使用 '*' 匹配( dp[i][j-1] )，要么 '*' 号前面的那个字符在匹配的过程当中一个都不使用（ dp[i][j-2] ），只要有一个是 true 则能够匹配。\n",
    "   \n",
    "最后考虑一下边界条件。一开始 i 是从 1 到 len(s) ，j 是 1 到 len(p) 。首先一来就能想到 dp[0][0] 是true，其他都是 false。但是这个边界条件是不够的。比如 isMatch(\"aab\", \"c * a * b\") ，dp[1][3] 应该是从 dp[0][2] 转移过来的，所以需要更多的边界条件，也就是一开始的 * 是能匹配空字符串的。所以我把 i 改到了从 0 开始,并且第二条也添加了 i=0，dp[i][j] = dp[i][j-2] 。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def isMatch(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        dp = []\n",
    "        dp = [[False for i in range(len(p)+1)] for j in range(len(s)+1)]\n",
    "        dp[0][0] = True\n",
    "#         print(dp)\n",
    "        for i in range(len(s)+1):\n",
    "            for j in range(1, len(p)+1):\n",
    "                if i > 0 and (s[i-1] == p[j-1] or p[j-1] == '.'):\n",
    "#                     print(\"1111111\",i)\n",
    "#                     print(\"2222222\",j)\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "#                     print(\"3333333\",dp[i-1][j-1])\n",
    "                if p[j-1] == '*':\n",
    "                    if i == 0 or (s[i-1] != p[j-2] and p[j-2] != '.'):\n",
    "#                         print(\"4444444\",i)\n",
    "#                         print(\"5555555\",j)\n",
    "                        dp[i][j] = dp[i][j-2]\n",
    "#                         print(\"6666666\",dp[i][j-2])\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i-1][j] or dp[i][j-1] or dp[i][j-2]\n",
    "#                         print(\"7777777\",i)\n",
    "#                         print(\"8888888\",j)\n",
    "#         print(dp)                       \n",
    "        return dp[len(s)][len(p)]\n",
    "    \n",
    "s = 'aa'\n",
    "p = 'a*'\n",
    "ss = Solution()\n",
    "print(ss.isMatch(s, p))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
